<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Range Sum Query 2D - Immutable</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="range-sum-query-2d---immutable">Range Sum Query 2D - Immutable</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=PwDqpOMwg6U&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=40">https://www.youtube.com/watch?v=PwDqpOMwg6U&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=40</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/Immutable2DSumRangeQuery.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/Immutable2DSumRangeQuery.java</a></li>
</ul>
<h1 id="1-lc-304-range-sum-query-2d---immutable">1. LC 304. Range Sum Query 2D - Immutable</h1>
<ul>
<li><a href="https://leetcode.com/problems/range-sum-query-2d-immutable/">https://leetcode.com/problems/range-sum-query-2d-immutable/</a></li>
</ul>
<p>给定一个m x n 的矩阵 matrix[m][n]， 求指定的(row1, col1) 和 (row2, col2)限定的子矩阵元素和</p>
<p>解决思路就是</p>
<ol>
<li>
<p>先求 dp[i][j] 表示 (0, 0) 到 (i, j) 限定的子矩阵元素和</p>
<p>dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1]</p>
</li>
<li>
<p>所求答案 ans</p>
<p>ans = dp[row2][col2] - dp[row1-1][col2] - dp[row2][col1] + T[row1-1][col1]</p>
</li>
</ol>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">NumMatrix</span>:</span>

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">__init__</span><span class="hljs-params">(self, matrix: List[List[int]])</span>:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> matrix <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> matrix[<span class="hljs-number">0</span>]:
            self.dp = []
            <span class="hljs-keyword">return</span>
        m = len(matrix)
        n = len(matrix[<span class="hljs-number">0</span>])
        self.dp = [[<span class="hljs-number">0</span>] * (n + <span class="hljs-number">1</span>) <span class="hljs-keyword">for</span> _ <span class="hljs-keyword">in</span> range(m + <span class="hljs-number">1</span>)]
        
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, m+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n+<span class="hljs-number">1</span>):
                self.dp[i][j] = self.dp[i<span class="hljs-number">-1</span>][j] + self.dp[i][j<span class="hljs-number">-1</span>] - self.dp[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>] + matrix[i<span class="hljs-number">-1</span>][j<span class="hljs-number">-1</span>]
        

    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">sumRegion</span><span class="hljs-params">(self, row1: int, col1: int, row2: int, col2: int)</span> -&gt; int:</span>
        row1 += <span class="hljs-number">1</span>
        row2 += <span class="hljs-number">1</span>
        col1 += <span class="hljs-number">1</span>
        col2 += <span class="hljs-number">1</span>
        <span class="hljs-keyword">return</span> self.dp[row2][col2] - self.dp[row1<span class="hljs-number">-1</span>][col2] - self.dp[row2][col1<span class="hljs-number">-1</span>] + self.dp[row1<span class="hljs-number">-1</span>][col1<span class="hljs-number">-1</span>]

</div></code></pre>

    </body>
    </html>